package airthmetic.exercise.tree;

import java.util.LinkedList;
import java.util.Queue;

public class _104_二叉树的最大深度 {

    // BFS
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }

        Queue<TreeNode> queue = new LinkedList();
        queue.offer(root);
        int dept = 0;

        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i=0; i<size; i++){
                TreeNode n = queue.poll();
                if(n.left != null){
                    queue.offer(n.left);
                }
                if(n.right != null){
                    queue.offer(n.right);
                }
            }
            dept++;
        }

        return dept;

    }


    // DFS
    public int maxDepth2(TreeNode root) {
        if(root == null){
            return 0;
        }
        return Math.max(maxDepth2(root.left), maxDepth2(root.right)) + 1;
    }
}
